# -*- coding: utf-8 -*-
# @Time: 2021/8/12 14:54
# @File: problem-21.py
# @DESC: https://leetcode-cn.com/problems/merge-two-sorted-lists/


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        cur_l1 = l1
        head = ListNode(0)
        cur_l2 = l2
        data = []
        while cur_l1 != None or cur_l2 != None:
            # 在l2上选择一个节点插入
            if cur_l1 != None:
                data.append(cur_l1.val)
                cur_l1 = cur_l1.next
            if cur_l2 != None:
                data.append(cur_l2.val)
                cur_l2 = cur_l2.next
        data = sorted(data)
        p = head
        for i in data:
            node = ListNode(i)
            p.next = node
            p = p.next
        return head.next

    def list(self, ListNode):
        cur = ListNode
        while cur != None:
            print(cur.val)
            cur = cur.next


s = Solution()

l1 = ListNode(0)
l1.next = ListNode(1)
l1.next.next = ListNode(2)
l2 = ListNode(10)
l2.next = ListNode(11)
l2.next.next = ListNode(12)
l2.next.next.next = ListNode(13)
r = s.mergeTwoLists(l1, l2)
s.list(r)
